package com.wct.genetic;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author WEI
 * @date 2018/5/27 13:48
 */
public class TspGenetic {

    private int cityCount;
    private int[][] disMatrix;
    private Random random;

    public TspGenetic() {
        random = new Random(System.currentTimeMillis());
    }

    public TspGenetic(int cityCount, int[][] disMatrix) {
        this.cityCount = cityCount;
        this.disMatrix = disMatrix;
        random = new Random(System.currentTimeMillis());
    }

    /**
     * @param initNum 需要的解的个数
     * @return 解集
     */
    public List<TspSolution> getSolutionList(int initNum) {

        if (initNum <= 0) {
            throw new RuntimeException("solution count must > 0");
        }
        // 解集
        List<TspSolution> tspSolutionList = new ArrayList<TspSolution>(initNum);

        for (int i = 0; i < initNum; i++) {
            // 获取一条路径，起点城市随机选择
//            List<Integer> pathList = getPath(random.nextInt(cityCount));
            List<Integer> pathList = getPath(0);

            // 路径权重
            int weight = 0;
            for (int j = 1; j < pathList.size(); j++) {
                int current = pathList.get(j - 1);
                int next = pathList.get(j);
                weight += disMatrix[current][next];
            }
            // 一个可行解
            TspSolution tspSolution = new TspSolution();
            tspSolution.setPathList(pathList);
            tspSolution.setWeight(weight);

            // 把可行解添加到解集
            tspSolutionList.add(tspSolution);
        }
        return tspSolutionList;
    }

    /**
     * 从解集中根据适应度随机选择一个个体
     *
     * @param tspSolutionList 解集
     * @return 选择一个个体
     */
    public TspSolution getAncestor(List<TspSolution> tspSolutionList) {

        if (tspSolutionList == null) {
            throw new NullPointerException("tspSolutionList is null");
        }
        if (tspSolutionList.isEmpty()) {
            throw new RuntimeException("tspSolutionList is empty");
        }
        // 根据权重生成适应度（1/权重）数组（概率）
        double[] pro = new double[tspSolutionList.size()];
        for (int i = 0; i < pro.length; i++) {
            pro[i] = 1.0d / tspSolutionList.get(i).getWeight();
        }
        // 使用轮盘赌产生下一个个体的序号
        int next = nextDiscrete(pro);
        // 返回下一个个体；
        return tspSolutionList.get(next);
    }

    /**
     * 基因重组
     *
     * @param father 父亲
     * @param mother 母亲
     * @return 生成一个孩子
     */
    public TspSolution doCombined(TspSolution father, TspSolution mother) {

        if (father == null || mother == null) {
            throw new NullPointerException("father or mother is null");
        }
        // 父亲基因list
        List<Integer> geneFather = father.getPathList();
        // 母亲基因list
        List<Integer> geneMother = mother.getPathList();
        // 孩子基因组
        int[] geneChild = new int[cityCount];
        // 初始化孩子基因
        for (int i = 0; i < geneChild.length; i++) {
            geneChild[i] = -1;
        }
        // 从父亲中随机选择基因进行继承
//        int select;
//        for (int i = 0; i < (cityCount / 2); i++) {
//            select = random.nextInt(cityCount);
//            geneChild[select] = geneFather.get(select);
//        }
        // 取父亲奇数位基因
//        for (int i = 1; i < cityCount; i=i+2) {
//            geneChild[i] = geneFather.get(i);
//        }
        // 取父亲偶数位基因
        for (int i = 0; i < cityCount; i=i+2) {
            geneChild[i] = geneFather.get(i);
        }
        
        // 孩子中的空余基因位list
        List<Integer> flags = geneFlags(geneChild);
        // 从母亲中继承基因
        int k = 0;
        for (int v : geneMother) {
            // 如果孩子中没有母亲第i个基因
            if (!isRepeat(v, geneChild)) {
                // 把第i个母亲基因放到孩子的flags.get(k)位置
                geneChild[flags.get(k)] = v;
                k++;
            }
        }
        // 变异
        geneChild = doVariation(geneChild);
        // 路径顺序
        List<Integer> pathList = new ArrayList<Integer>(geneChild.length);

        for (int v : geneChild) {
            pathList.add(v);
        }
        // 权重
        int weight = 0;
        for (int j = 1; j < geneChild.length; j++) {
            int current = geneChild[j - 1];
            int next = geneChild[j];
            weight += disMatrix[current][next];
        }

        // 孩子
        TspSolution child = new TspSolution();
        child.setPathList(pathList);
        child.setWeight(weight);

        return child;
    }

    private int[] doVariation(int[] gene) {
        if (random.nextBoolean()) {
            int seq1 = random.nextInt(gene.length);
            int seq2 = random.nextInt(gene.length);

            int temp = gene[seq1];
            gene[seq1] = gene[seq2];
            gene[seq2] = temp;
        }

        return gene;
    }

    /**
     * @param current 当前城市序号
     * @return 一个可行的访问路径
     */
    private List<Integer> getPath(int current) {
        // 访问标志位数组
        boolean[] flags = new boolean[cityCount];
        flags[current] = true;
        // 解的路径
        List<Integer> pathList = new ArrayList<Integer>(cityCount);
        pathList.add(current);

        int r;
        // 访问所有的城市
        while (!isAllVisit(flags)) {
            // 下一个访问的城市
            r = random.nextInt(cityCount);
            // 判断下一个城市是否访问过
            if (!flags[r]) {
                // 未访问过，把城市序号放到pathList中，并把该城市的访问标志置为true
                pathList.add(r);
                flags[r] = true;
            }
        }
        return pathList;
    }

    /**
     * true-访问完所有城市
     * false-未访问完所有城市
     *
     * @param flags 访问标志数组
     * @return 是否访问完所有城市
     */
    private boolean isAllVisit(boolean[] flags) {
        if (flags == null) {
            throw new NullPointerException("flags is null");
        }
        if (flags.length == 0) {
            throw new RuntimeException(" flags is empty");
        }
        // 遍历标志位数组 flags
        for (boolean v : flags) {
            // 判断城市是否已访问，只要有一个城市未访问则返回false
            if (!v) {
                return false;
            }
        }
        return true;
    }

    /**
     * @param geneChild 孩子基因组
     * @return 孩子基因组中的空余基因位列表
     */
    private List<Integer> geneFlags(int[] geneChild) {
        if (geneChild == null) {
            throw new NullPointerException("geneChild is null");
        }
        if (geneChild.length == 0) {
            throw new RuntimeException(" geneChild is empty");
        }
        // 空余基因位列表
        List<Integer> flags = new ArrayList<Integer>(geneChild.length);
        // 遍历孩子的基因组
        for (int i = 0; i < geneChild.length; i++) {
            if (geneChild[i] == -1) {
                // 如果第i个基因没有从父母继承，把i放到list中
                flags.add(i);
            }
        }
        return flags;
    }

    /**
     * 判断基因是否重复
     * true-重复
     * false-不重复
     *
     * @param seq  代检查基因
     * @param gene 基因组
     * @return 检查结果
     */
    private boolean isRepeat(int seq, int[] gene) {
        if (gene == null) {
            throw new NullPointerException("gene is null");
        }
        if (gene.length == 0) {
            throw new RuntimeException(" gene is empty");
        }
        for (int v : gene) {
            if (v == seq) {
                return true;
            }
        }
        return false;
    }

    /**
     * 轮盘赌函数
     *
     * @param pro 各类对象概率分布
     * @return 生成的对象类
     */
    private int nextDiscrete(double[] pro) {
        if (pro == null) {
            throw new NullPointerException("pro is null");
        }
        if (pro.length == 0) {
            throw new RuntimeException(" pro is empty");
        }
        double sum = 0;
        for (double v : pro) {
            sum += v;
        }
        //随机产生一个概率
        double rand = random.nextDouble() * sum;
        sum = 0;
        // pointer指示每个区段的右边界，从左往右扫描判断
        for (int i = 0; i < pro.length; i++) {
            sum += pro[i];
            if (Double.compare(rand, sum) <= 0) {
                return i;
            }
        }
        return pro.length - 1;
    }
}
